//单链表的排序：https://www.nowcoder.com/share/jump/3513649281733021022833
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        vector<ListNode*> vt;
        ListNode *cur = head;
        while (cur)
        {
            vt.push_back(cur);
            cur = cur->next;
        }
        //按val排序
        std::sort(vt.begin(), vt.end(), [](ListNode* p1, ListNode* p2){return p1->val < p2->val;});
        //重新组织链接关系
        ListNode* new_head = cur = nullptr;
        for (auto& e : vt)
        {
            if (new_head)
            {
                cur->next = e;
                cur = cur->next;
            }
            else 
            {
                new_head = cur = e;
            }
        }
        cur->next = nullptr;
        return new_head;
    }
};

//链表中环的入口节点：https://www.nowcoder.com/share/jump/3513649281733020968123
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        //方法1：使用map或set存储，第一次出现重复节点即为入口节点
        //时间和空间复杂度O(N)
        /*
        set<ListNode*> st;
        ListNode* cur = pHead, *answer = nullptr;
        while (cur)
        {
            pair<set<ListNode*>::iterator, bool> pa = st.insert(cur);
            if (!pa.second) 
            {
                answer = cur;
                break;
            }
            cur = cur->next;
        }
        return answer;
        */

        //方法2：快慢指针
        //时间复杂度O（N），空间复杂度O(1)
        ListNode* slow  = pHead;
        ListNode* fast = pHead;
        int flag  = 0;
        while (fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) 
            {
                flag = 1;
                break;
            }
        }
        ListNode* answer = pHead;
        if (flag)
        {
            ListNode* cur = slow;
            while (answer->next != cur->next || slow == pHead)
            {
                //特殊处理，所有节点构成环
                if (cur == pHead) {return cur;};

                answer = answer->next;
                cur = cur->next;
            }
            if (answer) {return answer->next;}
        }
        return nullptr;
    }
};